//
//  SqListExt.hpp
//  DataStructure
//
//  Created by 劢克科技 on 2020/6/22.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#ifndef SqListExt_hpp
#define SqListExt_hpp

#include <stdio.h>
#include "SqList.hpp"

// 测试功能，获取表长
int getListLenth(SqList L);

// 删除最小值，返回最小值，然后用最后一个元素填补
bool deleteMinimum(SqList &L, int &e);

// 高效逆序，要求空间复杂度为O(1)
bool listReverse(SqList &L);

// 时间复杂度O(n)空间复杂度O(1)删除所有值为x的元素
bool removeX(SqList &L, int x);

// 有序顺序表删除s和t之间的所有值
bool delRange(SqList &L, int s, int t);

// 顺序表删除s和t之间的所有值
bool delRangeNormal(SqList &L, int s, int t);

// 删除有序顺序表中重复的元素
bool delRepeat(SqList &L);

// 两个有序顺序表合并为一个并返回
bool mergeList(SqList L1, SqList L2, SqList &L);

// A[m+n]中存在2个线性表(a1,a2...am)(b1,b2...bn)
// 转换为(b1,b2...bn)(a1,a2...am)
void innerArrayReverse(int *A, int m, int n);

// a1,a2...an递增有序，找到最小元素x。
// 若找到则与后继元素交换，找不到则插入使其任然有序
void fundx(int *A, int len ,int x);

// (X0,X1...Xn-1) -> (Xp,Xp+1...Xn-1,X0,X1...Xp-1)
void moveArray(int *arr, int n, int p);

// 中位数：中间的数
// 等长的A和B，找出它们的中位数。
int searchMidNumber(int *A, int *B, int n);

// 主元素：m个相同的值，m > n / 2
// 找到数组中的主元素并返回，否则返回-1
int searchMainElement(int *arr, int n);

// 给定一个n个整数的数组，找出未出现的最小正整数
int searchMinNumber(int *arr, int n);

#endif /* SqListExt_hpp */
